package leetbook.stack;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 数据流的中位数
 * 思路：维护两个堆，一个大顶堆用于存放小的一半数字，一个小顶堆用于存放大的一半数字
 * 尽量维持两个堆元素均衡，最多相差不超过1
 * 取中位数时，若二堆size相同，取二堆顶平均；若二堆size不等，取较大者的堆顶。
 * 添加数字时要注意来到的数字和两个堆堆顶的大小关系以及两个堆size：
 */
public class Solution295 {

    public static void main(String[] args) {
        Solution295 s = new Solution295();
        s.addNum(1);
        s.addNum(2);
        System.out.println(s.findMedian());
        s.addNum(3);
        System.out.println(s.findMedian());
    }

    PriorityQueue<Integer> minHeap, maxHeap;

    /** initialize your data structure here. */
    public Solution295() {
        minHeap = new PriorityQueue<>((x,y)->y-x);
        maxHeap = new PriorityQueue<>();
    }

    public void addNum1(int num) {
        //先把num放在应在的堆
        if(maxHeap.size()!=0&&num>=maxHeap.peek()) maxHeap.offer(num);
        else minHeap.offer(num);
        //调整二堆size平衡
        if(minHeap.size()-maxHeap.size()>1)
            maxHeap.offer(minHeap.poll());
        if(maxHeap.size()-minHeap.size()>1)
            minHeap.offer(maxHeap.poll());
    }

    public void addNum(int num) {
        //一直保持maxHeap比minHeap元素多1或者相等
        if(minHeap.size()!=maxHeap.size()){
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if(minHeap.size()!=maxHeap.size()){
            return maxHeap.peek();
        }else {
            return 1.0*(minHeap.peek()+maxHeap.peek())/2;
        }
    }

    public double findMedian1() {
        if(minHeap.size()>maxHeap.size()){
            return minHeap.peek();
        }else if(minHeap.size()<maxHeap.size()){
            return maxHeap.peek();
        }else {
            return 1.0*(minHeap.peek()+maxHeap.peek())/2;
        }
    }

}
